perm filename RENEW.82[W82,JMC] blob
sn#652361 filedate 1982-04-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \input macro.tex[1,ffl]
C00009 ENDMK
C⊗;
\input macro.tex[1,ffl]
\topspace 1.5 in
\nopagenumber
\noindent
\ctrline{\bf Progress Report}
\vskip 5pt
\ctrline{\bf on}
\vskip 5pt
\ctrline{\bf National Science Foundation Grant MCS 81-04877}
\yyskip
\ctrline{\bf Basic Research in Artificial Intelligence}
\vskip 2 in
\ctrline{John McCarthy}
\vskip 2pt
\ctrline{Professor of Computer Science}
\vskip 2pt
\ctrline{Principal Investigator}
\vskip .5 in
\ctrline{Computer Science Department}
\vskip 5pt
\ctrline{Stanford University}
\vskip 5pt
\ctrline{Stanford, California}
\eject
This is a request to continue for a second year the grant
MCS-8104877 (Basic Research in Artificial Intelligence).
\yskip
During the past year I made some progress on the following problems:
\yskip
\outlineone 1.: Representation of facts about people's knowledge for use
in AI systems. The main results concern the need to represent such
facts as
\yskip
\outlinetwo A.: All a person $S$ knows about $X$ is that it satisfies the
sentence $p(X)$. This is required if
one is to be able to conclude that he still won't know fact $P1$ if he learns
fact $P2$. Delimiting knowledge is a problem that hasn't been attacked before
either in AI or in philosophy.
\vskip 5pt
\outlinetwo B.: A person knows about (say) oriental rugs. This can be
said by a person who doesn't himself know about oriental rugs, so
he can't express it as an assertion that the expert knows some
particular facts. Moreover, it needn't even be determined (whether
one knows it or not) what functions and predicates the expert uses
to express his knowledge. Nevertheless, formalization of "knowing
about" is needed if AI programs are to decide to consult experts -
whether they be humans or other programs.
\yskip
Problem A is partially solved by writing
$$∀x.p(x) ⊃ ¬ knows(S, Not Equal(X, Concept1(x))$$
in the formalism of my "First order theories of individual
concepts and propositions" or in a possible worlds formulation with a
Kripke-type accessibility relation
$$∀x.p(x) ⊃ ∃w.a(RW,w,S) ∧ value(X,w) = x$$
I don't yet know how to solve problem B.
\yskip
\outlineone 2.: I have become interested in Kowalski's doctrine that
$$progam = logic + control$$
In order to make it work, some very powerful methods are needed for expressing
control. The attached paper presented at the Logic Programming Conference
held at Long Beach describes a map-coloring problem, a PROLOG program giving its
logic, nd the problem of expressing
certain "postponement heuristics" as
control applied to that logic. Prolog has turned out to be a
good vehicle for thinking about such problems.
\yskip
\outlineone 3.: I have recently developed a first order theory of
what I call "dirty Lisp" programs, i.e. those involving imbedded SETQs,
RPLACA and RPLACD. It looks like I can prove correctness of
such programs. It involves the notion of the S-expression pointed
to by a location in a memory state. Thus it turns out that the
theory of clean Lisp is an essential component of the theory of
dirty Lisp - not merely that the theory of dirty Lisp is a generalization
of the theory of clean Lisp, as I and others had previously thought.
\yskip
During the forthcoming year I expect to work on all these
problems.
\vfill\eject\end